/*
 * 大根堆: 根节点比左右孩子节点的值都大
 * 已知孩子节点下标为i: 父亲节点(i-1)/2
 * 已知父亲节点下标为i: 左子节点 2*i+1 右子节点 2*i+2
 *
 * 最后一颗子树的根节点 ((len-1)-1)/2
 * len-1: 最后一个节点的下标
 * */

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class BigHeap {
    int[] elem;
    int size;

    public BigHeap(int capacity) {
        elem = new int[capacity];
    }

    public void initHeap(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            size++;
        }
    }

    public void createHeap() {
        for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, size);
        }
    }


    public int poll(){
        int temp = elem[0];
        swap(0, size);
        size--;
        // 调整完之后需要进行先下调整,因为原来的最后一个元素变成了堆顶元素,不用想的肯定不满足大根堆的结构
        shiftDown(0, size);
        return temp;
    }

    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;

        // 对交换引起的堆结构的改变进行调整(如果改变就调整)
        while (child < len) {
            // 找出左右孩子中最大的孩子,用child进行记录
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }

            // 判断大小关系
            if (elem[child] > elem[parent]) {
                swap(child,parent);

                // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2 * parent + 1;
            } else {
                // 左孩子为空,表示以最开始的parent为根的二叉树已经是大根堆结构
                break;
            }
        }

    }

    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }

        elem[size] = val;
        shiftUp(size);
        size++;
    }

    private void shiftUp(int child) {
        while (child != 0) {
            int parent = (child - 1) / 2;
            if (elem[parent] < elem[child]) {
                swap(child,parent);
                child = parent;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return elem.length == size;
    }

    public void swap(int i,int j){
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }


    class MyPriorityQueue {
        // 演示作用，不再考虑扩容部分的代码
        private int[] array = new int[100];
        private int size = 0;

        public void offer(int e) {
            array[size++] = e;
            shiftUp(size - 1);
        }

        public int poll() {
            int oldValue = array[0];
            array[0] = array[size--];
            shiftDown((size-1-1)/2,size);
            return oldValue;
        }

        public int peek() {
            return array[0];
        }
    }

    public static void main(String[] args) {
        BigHeap bigHeap = new BigHeap(10);
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        bigHeap.initHeap(array);

        bigHeap.createHeap();

        bigHeap.offer(80);

        int poll = bigHeap.poll();

        System.out.println(poll);

        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        queue.peek();

    }
}


/*
* top-k 问题 : 取出给定数据中前k个最小或者最大的元素
* 方法1: 将数据全部入优先级队列
* 缺点: 数据可能无法全部存入,内存不足,即使完全存入,效率也不是很高,不建议
*
* 方法2: 将k个元素入优先级队列,遍历剩余的元素,如果比堆顶元素大(小),入堆
* */

/*
* 堆排序: 调整为大根堆 让第一个元素和最后一个未排序的元素进行交换 很简单的一个排序
* */
